package 链表;

public class 奇偶链表 {
    public static void main(String[] args) {
        奇偶链表 test = new 奇偶链表();
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        test.oddEvenList(n1);
    }


    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }

        ListNode firstNode = null;
        ListNode secondNode = null;
        ListNode secondHead = null;

        ListNode curNode = head;

        int index = 1;
        while (curNode != null) {
            if (index % 2 != 0) {
                //奇数
                if (firstNode == null) {
                    firstNode = curNode;
                } else {
                    firstNode.next = curNode;
                    firstNode = curNode;
                }
            } else {
                //    偶数
                if (secondNode == null) {
                    secondNode = curNode;
                    secondHead = curNode;
                } else {
                    secondNode.next = curNode;
                    secondNode = curNode;
                }
            }
            curNode = curNode.next;
            index++;
        }
        firstNode.next = secondHead;
        secondNode.next = null;

        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
